/*
 * @Author: szx
 * @Date: 2022-04-02 18:43:44
 * @LastEditTime: 2022-04-02 18:59:27
 * @Description:
 * @FilePath: \leetcode\剑指offerII\027\027.js
 */
var isPalindrome = function (head) {
    let mid = middleNode(head);
    let last = reverseList(mid.next);
    mid.next = null;
    return isSame(head, last);
};

const middleNode = function (head) {
    let slow = new ListNode(-1, head);
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

const reverseList = function (head) {
    let prev = null;
    let cur = head;
    while (cur != null) {
        const next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
};

const isSame = function (headA, headB) {
    while (headA && headB) {
        if (headA.val !== headB.val) return false;
        headA = headA.next;
        headB = headB.next;
    }
    if (!headA && !headB) return true;
    else if ((headA && !headA.next) || (headB && !headB.next)) return true;
    else return false;
};
